import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//import java.util.ArrayList;
//import java.util.Arrays;
//import java.util.HashMap;
//import java.util.List;
//
public class Main {
    public static void main(String[] args) {
        int[] nums={1,2,3};
        System.out.println(permute(nums));
    }

    public static List<List<Integer>> permute(int[] nums){
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> output =new ArrayList<>();
        boolean[] ob = new boolean[21];
        for(int i=0;i<nums.length;i++){
            ob[nums[i]+10]=true;
        }
        int n=nums.length;
        signArray(list,output,ob,0,21,0,n);
        return list;
    }
    public static void signArray(List<List<Integer>> list,List<Integer> output,boolean[] ob,int count,int n,int first,int last){
        if(count>=last) list.add(new ArrayList<Integer>(output));
         int a=0;

        while(count<last){
            if(a==last-count) break;
            while(ob[first]){
                output.add(first-10);
                a++;
                ob[first]=false;
                signArray(list,output,ob,count+1,n,first,last);
                output.remove(count);
                ob[first]=true;
                break;
            }
            first++;
            first=first%n;
//            if(a==9)break;
        }

    }
//    public static void main(String[] args) {
////        int[] arr={2,-3,0,-2,-5,-5,-4,1,2,-2,2,0,2,-4,5,5,-10};
////        System.out.println(threeSum(arr));
//
//        int[] arr={-1,2,1,-4};
//        System.out.println(threeSumClosest(arr,1));
//    }
//
//    public static int threeSumClosest(int[] nums, int target) {
//        int num = 0;
//        boolean an=false;
//        Arrays.sort(nums);
//        for(int i=0;i<=nums.length-1-2;i++){
//            if(i>0&&nums[i]==nums[i-1]) continue;
//            int start=i+1;
//            int end=nums.length-1;
//            while(start<end){
//                if(start>i+1&&nums[start]==nums[start-1]) {
//                    start++;
//                    continue;
//                }
//                if(end<nums.length-1&&nums[end]==nums[end+1]){
//                    end--;
//                    continue;
//                }
//                int amount=nums[i]+nums[start]+nums[end];
//                if(an==false) num=amount;
//
//                if(an==true&&Math.abs(amount-target)<Math.abs(num-target)) num=amount;
//                an=true;
//                if(amount>target){
//                    end--;
//                }else{
//                    if(amount<target){
//                        start++;
//                    }else{
//                        return amount;
//                    }
//                }
//            }
//        }
//        return num;
//    }

//    public static List<List<Integer>> threeSum(int[] nums) {
//        List<List<Integer>> list = new ArrayList<>();
//        quickSort(nums);
//        for(int i=0;i<=nums.length-1-2;i++){
//            if(nums[i]>0) break;
//            if(i>0&&nums[i]==nums[i-1]) continue;
//            int start=i+1;
//            int end=nums.length-1;
//            while(start<end){
//                ArrayList<Integer> list1 = new ArrayList<>();
//                int add=nums[start]+nums[end];
//
//                if(add==-nums[i]){
//                    list1.add(nums[i]);
//                    list1.add(nums[start]);
//                    list1.add(nums[end]);
//                    list.add(list1);
//                    start++;
//                    end--;
//                    while(start<end&&nums[start]==nums[start-1]){
//                        start++;
//                    }
//                    while(end>start&&nums[end]==nums[end+1]){
//                        end--;
//                    }
//                    continue;
//                }
//                else if(add>-nums[i]){
//                    end--;
//                }else{
//                    if(add<-nums[i]){
//                        start++;
//                    }
//                }
//            }
//
//
////        int num1=100000;
////        int num2=100;
////        int num3=0;
////        for(int i=0;i<=nums.length-1-2;i++){
////            if(i>0&&nums[i]==nums[i-1]) continue;
////            for(int j=i+1;j<=nums.length-1-1;j++){//
////                // if(nums[j]==nums[j-1]) continue;
////                for(int end=nums.length-1;end>j;end--){//
//////                    if(end<nums.length-1&&nums[end]==nums[end+1]) continue;
////                    ArrayList<Integer> list1 = new ArrayList<>();
////                    if(nums[i]+nums[j]+nums[end]==0&&!(nums[i]==num1&&nums[j]==num2&&nums[end]==num3)){
////                        list1.add(nums[i]);
////                        list1.add(nums[j]);
////                        list1.add(nums[end]);
////                        list.add(list1);
////                        num1=nums[i];
////                        num2=nums[j];
////                        num3=nums[end];
////
////                        break;
////                    }
////                }
////            }
//        }return list;
//    }




    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int left,int right){
        if(left>=right) return ;
        int mid = (left+right)/2;
        int index=tmpMid(array,left,mid,right);
        swap(array,index,left);

        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    private static int tmpMid(int[] array,int left,int mid,int right){
        if(array[left]>array[right]){
            if(array[mid]<array[right]){
                return right;
            }else if(array[mid]>array[left]){
                return left;
            }else return mid;
        }else {
            if(array[mid]>array[right]) return right;
            else if(array[left]>array[mid]) return left;
            else return mid;
        }
    }
    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    private static void swap(int[] array,int index1,int index2){
        int tmp = array[index1];
        array[index1]=array[index2];
        array[index2] = tmp;
    }
}
//public class Main {
//    public static void main(String[] args) {
//        System.out.println("Hello world!");
//    }
//
//    public List<List<String>> groupAnagrams(String[] strs) {
//        HashMap<String,String> hashMap = new HashMap<>();
//        List<List<String>> list = new ArrayList<>();
//
//        for(String e : strs){
//
//            char[] chs = e.toCharArray();
//            mergeSort1(chs);
//            hashMap.put(e, Arrays.toString(chs));
//        }
//
//        return
//    }
//    public static void mergeSort1(char[] array){
//        mergeSortTmp(array,0,array.length-1);
//    }
//
//    private static void mergeSortTmp(char[] array, int left, int right) {
//        if(left>=right) return ;
//        int mid = (left+right)/2;
//        mergeSortTmp(array,left,mid);
//        mergeSortTmp(array,mid+1,right);
//
//        merge(array,left,mid,right);
//    }
//
//    private static void merge(char[] array, int left,int mid, int right) {
//        int s1 = left;
////        int ei = mid;
//        int s2 = mid+1;
//        int e2 = right;
//        char[] arr = new char[right-left+1];
//        int i=0;
//        while(s1<=mid&&s2<=e2){
//            if(array[s1]<array[s2]){
//                arr[i]=array[s1];
//                s1++;
//                i++;
//            }else {
//                arr[i]=array[s2];
//                s2++;
//                i++;
//            }
//        }
//        while(s1<=mid){ //s1=0  mid =0
//            if (s1<=mid){
//                arr[i]=array[s1];
//                s1++;
//                i++;
//            }
//
//        }
//        while(s2<=e2){//s2=1  e2=1
//            if (s2<=e2){
//                arr[i]=array[s2];
//                s2++;
//                i++;
//            }
//        }
//        for (int j = left; j <= right; j++) {
//            array[j] = arr[j-left];
//        }
//    }
//}